The features of the present invention may be used in the printing arts and, more particularly, in digital image processing and electrophotographic printing. In digital image processing, there is a distinct advantage to being able to electronically magnify or reduce the digital data coincident with the actual scanning of the document. Generally, the advantage is manifest in the ability to run the video capture and processing hardware at a predetermined video rate up to the image scaling circuitry and thereafter increasing or decreasing the video rate. Hence, the hardware may be designed for a specific operating speed, without having to continuously respond to changes in signal timing or frequency. In addition, any increased data rates due to a magnification of the video signals, are delayed as long as possible, thereby minimizing the need for faster and typically more expensive digital components. Accordingly, the present invention provides a digital image scaling apparatus that may be used to provide real-time scaling of image signals while a document is being scanned.
While the desirability of electronic scaling may be apparent, few techniques, if any, operate without incurring some loss in the accuracy of the output or scaled image signals, or a severe degradation in the rates at which the signals are processed. The loss of accuracy generally occurs in two ways. The first is through the mathematical error introduced when a fractional value is represented using a binary value of limited size. For example, representing the fractional value of one-fifth with only three binary digits would require "rounding" the fraction to the nearest eighth, or 0.250, thereby introducing significant error. The second way error occurs is through the generation of a modified video signal when, in actuality, an input video signal should have simple been passed through the system to produce the output signal. In other words, the image scaling system failed to recognize an input image signal that correspond exactly with the position of an output image signal and, therefore, should have passed the input signal directly through the system without modification.
Two of the techniques which have been proposed for image scaling include nearest-neighbor and linear interpolation. Techniques of this type have applicability across a wide range of scanning products, for example the Xerox.RTM. 7650 Pro Imager.RTM. and electronic reprographic systems such as the Xerox.RTM. Docutech Production Publisher.RTM.. The following disclosures may be relevant with regard to some of the approaches used for digital image scaling.
______________________________________ US-A-4,275,450 Patentee: Potter Issued: June 23, 1981 US-A-4,587,621 Patentee. DuVall Issued: May 6, 1986 US-A-4,742,553 Patentee: Irwin Issued: May 3, 1988 US-A-4,809,083 Patentee: Nagano et al. Issued: February 28, 1989 US-A-4,918,542 Patentee: Nagashima et al. Issued: April 17, 1990 US-A-5,008,752 Patentee: Van Nostrand Issued: April 16, 1991 US-A-5,025,405 Patentee: Swanson Issued: June 18, 1991 WO-91/01527 Inventor: Newman Published: February 7, 1991 ______________________________________
The relevant portions of the foregoing patents may be briefly summarized as follows:
U.S. Pat. No. A-4,275,450 to Potter discloses a magnification/demagnification apparatus and method wherein an accumulator is used to accumulate a reduction ratio, which, when greater than a predefined threshold, signals that the image signal should be passed on. Otherwise, the image signal is deleted and an additive reset count is added to the accumulator. In an alternative embodiment, an add-one circuit generates a signal which temporarily increases a magnification counter setting by one. The add-one circuit is only activated at selected times when the value in the magnification counter exceeds a threshold value.
U.S. Pat. No. A-4,587,621 to DuVall discloses a device for magnification of image signals wherein a linear interpolator is used to calculate magnification ratios. The interpolator determines a spatial relationship of output values, with respect to a pair of digital scan values, where the spacing between successive scan outputs is defined as the reciprocal of a magnification value. A hardware circuit, which accumulates a magnification value and subsequently interpolates an input image to determine if an output pixel is valid, is used. Furthermore, the accumulated value is also used as an input to a large look-up table to determine the interpolated output value.
U.S. Pat. No. A-4,742,553 to Irwin discloses a resolution conversion system for bitmap images using error term averaging, wherein an error value is added to an input value to generate an output value and a test value. An algorithm is disclosed which implements the resolution conversion and is particularly suitable for greyscale processing.
U.S. Pat. No. A-4,809,083 to Nagano et al. discloses an image recording/reading apparatus with enlarging and reducing functions, wherein a desired magnification is divided into an integer part and a decimal part. The decimal part is then used to correct an image output. Every time the accumulated decimal part is greater than one, an output pixel is deleted.
U.S. Pat. No. A-4,918,542 to Nagashima et al. discloses an image processing apparatus capable of smooth multi-area variable magnification, wherein an error term is determined by comparing a desired image magnification ratio with an actual image magnification ratio. Two counters are initially set to zero and count a number of output pixels and a number of input pixels. A signal, RDEB, stores an error term which is used to pad image output data. An algorithm is shown in FIGS. 10A, 10B, 11A, and 11B which pads an input image. The algorithm also determines if an output pixel is valid.
U.S. Pat. No. A-5,008,752 to Van Nostrand discloses an interpolator for enlarging or reducing a digital image in two dimensions, which includes row and column interpolators. Both interpolators operate so as to generate signals indicating when the next element, row, or pixel is to be retrieved. The interpolators also produce a displacement address which is used to retrieve an interpolation coefficient from a look-up table, the interpolation coefficient being used subsequently to produce the interpolated output.
U.S. Pat. No. A-5,025,405 to Swanson discloses a subsystem capable of image synthesis in a computer workstation. In general, the images to be displayed are represented by a function, wherein the values across an area, i.e., color or intensity, must be interpolated to accurately reflect the image. The system employs interpolation, based on precomputed integer and fractional portions of the function's slope, to scale the function using integer arithmetic.
WO-91/01527 by Newman discloses an interpolation system that generates an interpolated value in response to an input value. The system includes a function value store, an address generator, and an interpolator. In operation, the address generator is used to generate address signals to identify locations in the function value store, which in turn provides function values that are used in conjunction with the input value to generate the interpolated value.
The present invention seeks to overcome limitations found in the related references and commercially available products by providing an apparatus for accurately scaling the video signals of a digital image or document during the scanning or processing of the digital signals. The present invention also enables the scaling of video signals across a range of scaling ratios, without the need for large look-up tables to produce the interpolated output. Furthermore, the present invention provides the scaling functionality in a highly accurate manner using an efficient hardware implementation that minimizes memory requirements. In addition, the present invention enables the use of programmable scaling ratios, thereby increasing the flexibility of the apparatus.
In accordance with one aspect of the present invention, there is provided an improved digital image scaling apparatus having digital hardware capable of scaling the size of an image, represented by a plurality of input video signals by a desired scaling ratio, a controller for producing a scale factor, and a scale factor valid signal, where the controller includes a padder suitable for increasing the accuracy of the scale factor. The apparatus further includes an interpolator or calculator for producing an output signal as a function of one or more input video signals, in response to the scale factor and scale factor valid signal.
In accordance with another aspect of the present invention, there is provided a digital scaling apparatus suitable for scaling an orthogonally oriented array of digital image signals in two dimensions, where the array is arranged by rows of scanlines comprised of a plurality of pixels. The apparatus employs a single controller for producing both a first scale factor for use by a scanline interpolator, and a second scale factor suitable for use by a pixel interpolator. The apparatus further employs a padder suitable for supplementing the scale factor so as to increase the accuracy of the interpolated output.
Pursuant to yet another aspect of the present invention, there is provided a method for scaling an input image represented by a plurality of pixel values to produce an output image. The method beings by obtaining two successive input pixel values, P.sub.n and P.sub.n+1. At the same general time, an arithmetic accumulation of the sum of a seed value, a previously accumulated sum, and a supplemental value is being calculated, the accumulated sum having both integer and fractional portions. Once determined, the integer portion of the accumulated sum is used to determine whether the first and second input pixel values are to be used to produce an output pixel value. If so, the accumulated sum is used to generate a scale or interpolation factor, .alpha., based upon the fractional portion of the accumulated sum, which, in turn, is utilized in interpolating between the first and the second pixel values to produce an output pixel value P.sub.new, where: EQU P.sub.new =P.sub.n+1 +.alpha.(P.sub.n -P.sub.n+1).
The accumulation and interpolation steps are repeated until no further output pixels are to be generated from the current input pixels. At that time, the second input pixel value is shifted to become the new value for P.sub.n, a new P.sub.n+1 pixel value is obtained, and the process continues with the accumulation and interpolation steps, until all of the input pixels have been processed in a similar manner.